package src.array;

public class no53 {  //最大子数组和

    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        //动态规划，利用dp作为前缀和数组，存 i 处当前能累计的最大值
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;

    }

    //只不过每个状态只与前一个状态有关，所以为了降低空间复杂度可以只用一个变量来保存
    public int maxSubArray2(int[] nums) {
        int sum = 0;
        int ans = nums[0];
        //当前最大连续子序列和为 sum，结果为 ans
        //如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
        //如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
        //每次比较 sum 和 ans的大小，将最大值置为ans
        for (int num : nums) {
            if (sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }


}
